Routing permutations and involutions on optical ring networks: complexity results and solution to an open problem

Abstract

Given a network G and a demand D of communication requests on G, a routing for (G, D) is a set of directed paths of G, each from the source to the destination of one request of D. The Routing and Wavelength Assignment Problem seeks a routing R for (G, D) and an assignment of wavelengths to the directed paths in R such that the number of wavelengths used is minimized, subject to that any two directed paths with at least one common arc receive distinct wavelengths. In the case where G is a ring, this problem is known as the Ring Routing and Wavelength Assignment Problem (RRWA). If in addition D is symmetric (that is, (s, t) ∈ D implies (t, s) ∈ D) and the directed paths for requests (s, t) and..